package 链表.双向链表;

/*
 * 双向链表  不带哨兵位的双向链表
 * 思路分析:
 * Node: 节点类
 * List: 链表
 * Head: 链表的头
 * Prev: 指向上一个元素
 * Next: 指向下一个元素
 * */
public class List {
    private Node head;// 头结点

    public List() {

    }

    public void addNode(int val) {
        Node node = new Node(val);
        if (IsEmpty()) {
            // 链表为空,该节点为新头
            head = node;
        }

        Node cur = head;

        while (cur.next != null) {
            cur = cur.next;
        }

        // 此时的cur就表示最后一个节点
        cur.next = node;
        node.prev = cur;
    }

    public void addFirst(int val){
        Node newNode = new Node(val);
        if(IsEmpty()){
            head = newNode;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    // 根据节点的no值删除节点
    public void DeleteNode(int no) {
        int count = 0;// 记录被删除节点的个数

        if(IsEmpty()){
            System.out.println("链表为空");
            return;
        }
        Node cur = head;// 将head的值赋给变量cur,使其代替head进行循环遍历
        while(true){
            if(cur == null){
                System.out.println("共删除了"+count+"个节点");
                // 链表中已经没有值为no的节点,跳出循环
                break;
            }

            if(cur.val == no){
                Node prev = cur.prev;// 记录将要被删除的节点的上一个节点
                cur = cur.next;// 用下一个节点覆盖当前节点
                cur.prev = prev;
                count++;
                continue;
            }
            cur = cur.next;
        }
    }

    // 根据索引查找节点
    public Node findNode(int index) throws IndexException {
        // 索引是否合法,一看到和索引相关的问题就应该要想一下是否需要判断索引的合法性,此处需要判断
        if(index < 0 || index >= getSize()){
            // 自定义异常来表示索引越界这种不合法的行为
            throw new IndexException("索引越界");
        }

        Node cur = head;
        while(index > 0){
            index--;
            cur = cur.next;
        }

        return cur;
    }


    /*
    * 链表中元素的个数
    * */
    public int getSize(){
        Node cur = head;

        int count = 0;

        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }

    /*
    * 判断链表是否为空
    * */
    public Boolean IsEmpty() {
        return head == null;
    }

}

// 节点类
class Node {
    int val;
    Node prev;
    Node next;

    public Node() {
    }

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + val +
                ", prev=" + prev +
                ", next=" + next +
                '}';
    }
}
